package com.mccken.practice.algorithm.tree_01;

import com.mccken.practice.algorithm.common.TreeNode_Common;

/**
 * 完全二叉树
 * 
 * @program: mccken-collect
 * @description:
 * @author: mccken
 * @create: 2023-12-12 22:07
 **/
public class CompleteBinaryTreeOperate {
	
	// 普通二叉树的节点数
	public static int countNodes_1(TreeNode_Common root) {
		if (root == null) {
			return 0;
		}
		return countNodes_1(root.left) + countNodes_1(root.right) + 1;
	}
	
	// 满二叉树的节点总数
	public static int countNodes_2(TreeNode_Common root) {
		int h = 0;
		while (root != null) {
			root = root.left;
			h++;
		}
		return (int)Math.pow(2,h)-1;
	}
	
	// 完全二叉树的节点数计算
	public static int countNode_3(TreeNode_Common root) {
		if (root == null) {
			return 0;
		}
		
		TreeNode_Common r = root;
		int rh = 0;
		while (r!= null) {
			r = r.right;
			rh++;
		}
		
		int lh = 0;
		TreeNode_Common l = root;
		while (l!= null) {
			l = l.left;
			lh++;
		}
		
		if (rh == lh) {
			return (int)Math.pow(2,lh)-1;	
		}
		return 1+countNode_3(root.left)+countNode_3(root.right);
	}
	
}
